A directed graph such as a directed acyclic graph may be employed by an application to represent a collection of data. For example, in at least some applications that are visually oriented, a ‘scene’ that is to be rendered by the application is organized by the application in the form of such a directed graph. For example, if the scene includes a room with a person in the room, the directed graph may include a root node or container at a first level and a person description node and room description node at the second level. At the third level and directly below the person node may be a head node, body node, and limb nodes for the person, each of which variously further defines body parts of the person. Likewise, at the third level and directly below the room node may be a plurality of wall nodes, each of which variously further defines walls within the room. As may be appreciated, further levels of nodes may be provided to even further define elements of the scene in a progressively more detailed manner. It is not atypical that a directed graph may have on the order of thousands of nodes, for example.
Thus, the directed graph defines every element of the scene such that each element is available for rendering a particular view within the scene. Notably, a particular view need not necessarily include every element within the scene/node within the directed graph. For example, in ‘looking’ in a particular direction, one or more walls of the room of the scene may not be ‘visible’. Likewise, depending on the granularity of the view, more finely detailed elements may or may not be discernible. For example, if the person is seen from afar in the view, the fingers of such person are not especially noticeable.
As may now be appreciated, then, to construct a view based on the directed graph, one or more actions are performed with regard to the directed graph to produce a cumulative effect. For example, one action may be to cull out nodes or containers of the graph that would not be visible based on the view looking in a particular direction. Another action may be to cull out nodes or containers of the graph that would not be visible based on being too finely detailed. A further action may be to actually draw the view based on the nodes or containers remaining after the culling action.
In general, to perform an action with regard to a directed graph, the directed graph is traversed and a method related to the action is applied to each node/container, where the method applied is based on the type of node/container. Typically, the traversal begins at the first level of the directed graph, and all ‘children’ of a node (i.e., (n)th level nodes depending from an (n−1)th level node) are dealt with prior to dealing with any ‘siblings’ of a node (i.e., nodes at the same (n)th level and all depending from an (n−1)th level node). Note, though, that traversal may also be accomplished based on any other methodology without departing from the spirit and scope of the present invention. Since the action method applied is specific to the type of node/container, the result of the action on any particular node/container depends on such type of node/containers and therefore can be radically different from container to container.
Typically, a core system provides the basic container types required to describe a scene and provides the basic actions to be performed on the graph/scene. Such basic actions may for example include drawing, computing the bounds, and writing data to a file. Such basic container types may for example include links, switches, and shapes. As may be appreciated, though, such a core system cannot anticipate all the types of actions and container types that might be required to implement desired functionality for a particular application.
Accordingly, a need exists for a mechanism to extend the functionality of the core system. In particular, a need exists for an extension mechanism that allows new container types to work with existing actions without having to re-develop such actions, and also that allows new actions to work with existing container types without having to re-develop such container types.
With such extension mechanism, the system can take on additional functionality as required. For example, the system can implement new hardware and software features and algorithms, and can support new hardware and software, all without the system being upgraded to a new version. The system thus has a high degree of fine-grained extensibility to for example allow hardware vendors to replace particular behaviors of objects and to allow software developers and customers to replace and extend algorithms where they have more knowledge to achieve their own differentiation and superior results. This requires the ability to add new/extended container types to the system with new user-defined data and behaviors, and to add new/extended actions to the system with new user-defined action methods. Moreover, this requires that existing container types support new actions, and that existing actions support new container types.